namespace AdvancedTraining.Lesson33;

/// <summary>
/// 寻找明星算法实现
/// 本题测试链接 : https://leetcode.cn/problems/find-the-celebrity/
///
/// 明星的定义：
/// 1. 明星不认识任何其他人（除了自己）
/// 2. 所有人都认识明星
///
/// 算法思路：
/// 1. 第一阶段：找到候选人
///    - 从0开始，如果当前候选人认识其他人，就更换候选人为该其他人
///    - 最终得到唯一可能的明星候选人
/// 2. 第二阶段：验证候选人
///    - 验证候选人是否不认识左边的人（0到cand-1）
///    - 验证所有人都认识候选人
/// </summary>
public class FindTheCelebrity //leetcode_0277
{
    /// <summary>
    /// 模拟的knows方法：x是否认识i
    /// 提交时不要提交这个函数，因为默认系统会给你这个函数
    /// knows方法，自己不认识自己
    /// </summary>
    /// <param name="x">询问者</param>
    /// <param name="i">被询问者</param>
    /// <returns>true表示x认识i，false表示x不认识i</returns>
    private static bool Knows(int x, int i)
    {
        // 这是一个模拟实现，在实际系统中这个函数由系统提供
        // 返回true表示x认识i，false表示x不认识i
        return false;
    }

    /// <summary>
    /// 寻找明星的主要算法
    /// </summary>
    /// <param name="n">总人数，编号从0到n-1</param>
    /// <returns>明星的编号，如果没有明星返回-1</returns>
    public int FindCelebrity(int n)
    {
        // 第一阶段：找到候选人
        // 调可能成为明星的人，谁就是cand
        var cand = 0;
        for (var i = 0; i < n; ++i)
        {
            if (Knows(cand, i))
            {
                cand = i;
            }
        }

        // 第二阶段：验证候选人
        // cand是什么？唯一可能是明星的人！
        // 下一步就是验证，它到底是不是明星

        // 1) 验证cand是不是不认识所有的人（左侧cand都不认识）
        // 因为在第一阶段中，cand右侧的人都被cand认识，所以cand不能认识右侧的人
        // 因此只需要验证0到cand-1的人
        for (var i = 0; i < cand; ++i)
        {
            if (Knows(cand, i))
            {
                return -1; // cand认识左侧的人，所以cand不是明星
            }
        }

        // 2) 验证是不是所有的人都认识cand
        for (var i = 0; i < n; ++i)
        {
            if (!Knows(i, cand))
            {
                return -1; // 有人不认识cand，所以cand不是明星
            }
        }

        return cand; // 通过所有验证，cand是明星
    }

    /// <summary>
    /// 测试寻找明星算法
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("寻找明星算法测试开始");

        // 由于实际的Knows方法由系统提供，我们通过模拟测试来验证算法逻辑
        Console.WriteLine("这是一个示例算法实现，实际提交时只需要提交FindCelebrity方法");
        Console.WriteLine("系统会自动提供Knows方法来测试算法的正确性");

        // 测试算法框架
        Console.WriteLine("\n算法框架验证：");
        Console.WriteLine("1. 第一阶段：通过线性扫描找到唯一候选者");
        Console.WriteLine("2. 第二阶段：验证候选者满足明星条件");
        Console.WriteLine("3. 时间复杂度：O(n)，空间复杂度：O(1)");

        // 创建测试实例
        var celebrity = new FindTheCelebrity();

        // 测试基本框架（n=0的情况）
        Console.WriteLine("\n测试用例1: n=0（空人员）");
        var result1 = celebrity.FindCelebrity(0);
        Console.WriteLine($"结果: {result1} (期望: -1，因为没有人员)");

        // 测试n=1的情况（只有一个人）
        Console.WriteLine("\n测试用例2: n=1（单个人）");
        var result2 = celebrity.FindCelebrity(1);
        Console.WriteLine($"结果: {result2} (期望: 0，因为单个人认识自己且被自己认识，但根据题意明星不认识其他人)");

        // 测试基本逻辑框架（由于Knows返回false，结果为0）
        Console.WriteLine("\n测试用例3: n=4（基本测试）");
        var result3 = celebrity.FindCelebrity(4);
        Console.WriteLine($"结果: {result3} (算法逻辑正确，结果取决于实际的Knows方法)");

        // 说明算法的正确性
        Console.WriteLine("\n算法正确性说明：");
        Console.WriteLine("- 第一阶段确保找到唯一可能成为明星的人");
        Console.WriteLine("- 第二阶段验证该人满足明星的两个条件");
        Console.WriteLine("- 如果存在明星，算法保证找到正确的明星");
        Console.WriteLine("- 如果不存在明星，算法返回-1");

        Console.WriteLine("\n寻找明星算法测试结束");
    }
}